package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/1/9 15:16
 */
public class PathSum2 {


    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new ArrayList<>();
        if (root == null){
            return paths;
        }
        pathSum(root, sum, new ArrayList<>(), paths);
        return paths;
    }


    public void pathSum(TreeNode node, int sum, List<Integer> path, List<List<Integer>> paths) {
        if (node == null){
            return;
        }
        path.add(node.val);
        sum -= node.val;
        if (sum == 0 && node.left == null && node.right == null){
            paths.add(path);
        }else {
            if (node.left != null){
                List<Integer>pathBranch = new ArrayList<>();
                pathBranch.addAll(path);
                pathSum(node.left, sum, pathBranch, paths);
            }
            if (node.right != null){
                List<Integer>pathBranch = new ArrayList<>();
                pathBranch.addAll(path);
                pathSum(node.right, sum, pathBranch, paths);
            }
        }
    }



    public static void main(String[]args){

        TreeNode node1 = new TreeNode(-2);
        TreeNode node2 = new TreeNode(-3);
//        TreeNode node3 = new TreeNode(3);
//        TreeNode node4 = new TreeNode(4);
//        TreeNode node5 = new TreeNode(5);
        node1.right = node2;
//        node2.right = node3;
//        node3.right = node4;
//        node4.right = node5;


        out.println(new PathSum2().pathSum(node1, -5));
    }
}
